\documentclass{ctexart}

\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{url}
\usepackage{caption}
\usepackage{float}
\usepackage{subfig}

\title{作业题4-37：利用二叉数查找k1,k2之间所有数}

\author{作者姓名:阮伟灿 \\ 作者专业和学号：统计学3210104141}


\begin{document}

    \maketitle

    \section{算法实现}
    （具体代码详细可以见AvlTree.h的429-446行）\\
    
     参考了contains的函数，相当于是contains加上了输出以及多了一个的条件。
     由于多了一个条件，所以if语句的情况由三种变为六种，
     将可能会产生的六种情况分别划分，时间复杂度为$\theta  =K+log(n)$
     （其中K为打印关键字的个数）。


    \section{一些细节}
   第429行我本来用了$*\&$来减少复制，但是不知道为什么总是报错，我就改回$*$了，但
   肯定是有很大一部分内存的浪费的。

    \section{数据泄漏}
    又是十分神奇地没有数据泄漏,但好像这个程序也没有什么可以泄漏的地方。

    \section{时间复杂度理论运算}
    该实验的时间复杂度为$\theta  =K+log(n)$，将分别证明时间复杂度为K和$log(n)$的情况。\\
    \subsection{K的情况}
    至少需要输出K个数，那么至少会执行K次指令。
    \subsection{$log(n)$的情况}
    当K足够少时，$log(n)$远远大于K，则和形成的AvlTree的深度有关，比如k1=k2=Max;
    则需要查找$log(n)$次才能找到k并将其输出

    \section{时间复杂度实际检验}
   \subsection{K的情况}
    取一个0-5000的乱序数组导入AvlTree，取k1=0,k2=500,1000,1500,2000,
    2500,3000
    ,3500,4500进行测验，计算运算时间，得到结果如下：(下面的时间都是多次运算取平均值得到的)\\
    
        
        \begin{tabular}{lllllllll}
        500 & 1000 & 1500 & 2000 & 2500 & 3000 & 3500 & 4000 & 4500  \\
        67  & 134  & 203  & 276  & 344  & 406  & 468  & 531  & 594  
        \end{tabular}

    \subsection{$log(n)$的情况}
    取一个0-$2^n$的乱序数组导入AvlTree，使k1=k2=$2^n-1$,取n=5,10,15
    ,20
    进行测验，计算运算时间，得到结果如下(因为两种情况时间相差过大，
    因而采用了不同的获取时间函数。此时判断函数contains的影响变大，所以暂时删去
    数据过大。只取了4组，再大算太久了，可能要用高精度？)：\\
        \begin{tabular}{cccc}
        5    & 10   & 15   & 20    \\
        1445 & 2418 & 3253 & 5166 
        \end{tabular}
    
   
    
    \section{结论}
    综上所述，结论成立。($log(n)$的情况误差很大，但我找不到解决方法了)

\end{document}
